package Tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 题目 ：二叉树的中序遍历
 * 题目详述 ：
 * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
 */
public class InorderTraversal {
    /**
     * 方法一 ：递归
     */
    /*
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>(); // 用来存储结果集合
        // dfs方法所传递的参数，即（当前正在遍历的树节点 ， list结果集合）
        dfs(root , list);
        return list;
    }
    public void dfs(TreeNode node , List<Integer> list){
        if(node == null){
            return;
        }
        // 遍历左子树，直至左节点不存在为止；
        dfs(node.left , list);
        // 将当前遍历节点加入到结果集合（由于（1）其没有左子节点/（2）其左子节点已经加入到结果集合中）
        list.add(node.val);
        dfs(node.right , list);
    }
     */
    /**
     * 方法二 ：迭代
     * 核心思想 :
     * （1）与上面的遍历是一致的，即中序遍历的核心在于遍历左子树；
     * （2）由于栈的特点是“先入后出”，
     * 以根节点为基础开始遍历整个二叉树的左子树，直至左子节点为null，同时需要将其遍历路径上的节点加入到栈中；
     * ===》 栈顶元素是当前遍历节点的父节点，层层递推；
     * 弹栈的条件 ；即与递归一致，若是当前遍历节点为空的话，则需要将当前遍历节点的父节点加入到栈中；
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>(); // 栈顶用来存放当前遍历节点的父节点
        TreeNode node = root; // 使用node节点，来指向root根节点
        while( node != null || !stack.isEmpty()){
            // 循环结束条件： （1）栈为空 | （2）node == null ，
            // 以上两个条件同时满足，即代表遍历完了所有元素，同时对于其进行了中序遍历；
            while( node != null){
                // 当前遍历的节点不为空的话，即需要将当前节点压入栈中，同时使得node指向当前遍历节点的左子节点
                stack.push(node);
                node = node.left;
            }
            // 若是当前节点为空，则需要将当前栈顶元素弹出（即，其指向当前节点的父节点）
            TreeNode popNode = stack.pop();
            result.add(popNode.val);
            // 节点指向弹出节点（当前遍历节点的父节点）的右子节点
            node = popNode.right;
        }
        return result;
    }
}
